home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Peter's Final Project / INFO < prev    next >
Text File  |  1995-05-10  |  4KB  |  83 lines
  1.  Peter's Final Project -- A texture mapping demonstration
  2.  © 1995, Peter Mattis
  3.  
  4.  E-mail:
  5.  petm@soda.csua.berkeley.edu
  6.  
  7.  Snail-mail:
  8.   Peter Mattis
  9.   557 Fort Laramie Dr.
  10.   Sunnyvale, CA 94087
  11.  
  12.  Avaible from:
  13.  http://www.csua.berkeley.edu/~petm/final.html
  14.  
  15.  This program is free software; you can redistribute it and/or modify
  16.  it under the terms of the GNU General Public License as published by
  17.  the Free Software Foundation; either version 2 of the License, or
  18.  (at your option) any later version.
  19.  
  20.  This program is distributed in the hope that it will be useful,
  21.  but WITHOUT ANY WARRANTY; without even the implied warranty of
  22.  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23.  GNU General Public License for more details.
  24.  
  25.  You should have received a copy of the GNU General Public License
  26.  along with this program; if not, write to the Free Software
  27.  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  28.  
  29. ---------------------------------------------------------------------
  30.  
  31. Goals:
  32.   There were several goals in doing this projected. The main one,
  33.   however, was to write a portable texture mapping demo. The project
  34.   was originally written under unix/X on an HP 9000. Shortly after
  35.   starting, I realized that the X11 specific functions could be 
  36.   contained within one file. The Macintosh port began and ended
  37.   the next day.
  38.  
  39. ---------------------------------------------------------------------
  40.  
  41. How it's done:
  42.   There are two major areas to the project. Scan conversion and
  43.   hidden surface removal.
  44.   
  45.   Scan conversion relies on the fact that for walls, each column
  46.   has a constant z value and for floors and ceilings, each row
  47.   has a constant z value. At the end of the day, this measn that
  48.   instead of performing a perspective divide at each pixel, we
  49.   only need to perform the perspective divide for each row or column.
  50.   This is a big big win and is the key fact that allows the demo
  51.   to run at any reasonable speed.
  52.   
  53.   There is one major idea to the whole hidden surface removal process.
  54.   That is, draw from front to back. The problem is to efficiently
  55.   determine when a pixel has already been drawn. The solution was
  56.   to maintain a span buffer. Spans of pixels that could be drawn into.
  57.   As pixels are drawn into the frame buffer, chunks are taken out
  58.   of the span buffer. When the buffer is empty, the screen is full
  59.   and scan conversion can end. This is the big win in drawing back
  60.   to front. Distant objects are never considered since scan conversion
  61.   ends before it even gets close to them. This does however complicate
  62.   the scan conversion loops, but they are still understandable, (I
  63.   think). 
  64.   
  65.   Note that any front to back drawing order will suffice, but there 
  66.   is still a "best" drawing order. I originally used bsp (binary
  67.   space partitioning) trees to determine this drawing order. This
  68.   produced a correct result. However, in certain areas of the maze,
  69.   drawing slowed to a crawl for no apparent reason. An closer
  70.   inspection I realized that it was drawing many faces that were
  71.   directly behind a face just drawn. These faces were of course not
  72.   visible, but determining that took a sizable percentage of drawing
  73.   time. I decided to change to use a graph based approach. Each node
  74.   of the graph is a sector in the world. A sector is a convex region.
  75.   Each sector is connected to neighboring regions. Starting from the
  76.   node in which the viewer is in, a breadth first search of the graph
  77.   will produce a back to front drawing order. Well, this isn't exactly
  78.   true, but for the purposes of a maze, it works. The drawing order
  79.   is better than a bsp tree's since it tends to draw sectors that are
  80.   visible. (Note, faces behind the viewer will be clipped, which is
  81.   a fairly quick operation). The demo looks the same as it did before,
  82.   but there is virtually no slow down no matter what size maze is used.
  83.